%% File name: chMathFoundations
%% Author: Anung B. Ariwibowo
%% History:
%%  2002.11.20 Start writing a template

\chapter{Analisa Algoritma} \label{ch:algorithm-analysis}


Pembahasan konsep Algoritma.

Contoh ilustrasi penggunaan algoritma untuk menyelesaikan masalah pengurutan bilangan \cite{cormen}.


\section{Dasar Matematika} \label{sect:math-foundations}

Sigma notation

\section{Big-Oh} \label{sec:big-oh}

Dengan menggunakan teknik pembuktian dengan kontradiksi, buktikanlah bahwa \(n^2\) \textbf{bukan} \(O(n)\).

Bukti:

Andaikan \(n^2\) adalah \(O(n)\), maka ada konstanta positif \(c\) dan \(n_0\) sedemikian sehingga \(n^2 \leq c n\) untuk semua \(n \geq n_0\).

Karena \(n\) bernilai positif, \[n^2 \leq n\] memberikan \[n \leq c\]. Tetapi tak mungkin ada konstanta \(c\) yang memenuhi \(c \geq n\) untuk semua \(n \geq n_0\).

Jadi \(n^2\) bukan \(O(n)\).

\[T(n) = O(f(n))\] menyatakan bahwa \(f(n)\) adalah suatu \textbf{batas atas} dari laju-pertumbuhan \(T(n)\). Bagaimana untuk menyatakan batas bawah? Gunakan notasi Omega-Besar: \(\Omega\).

Definisi:

\(T(n)\) adalah \(\Omega(g(n))\) jika dan hanya jika ada konstanta positif \(c\) dan \(n_0\) sedemikian sehingga \(T(n) \geq c g(n)\) untuk semua \(n \geq n_0\).

%% Ilustrasi grafik \Omega(g(n)) sebagai batas atas dari T(n).

Contoh:
\begin{enumerate}
  \item \(3n + 3 = \Omega(n)\) karena \(3n+3 \geq 3n\) untuk \(n \geq
      1\). (Di sini \(c=3\) dan \(n_0 = 1\))
  \item \(10n^2+4n+2 = \Omega(n^2)\) karena \(10n^2+4n+2 \geq n^2\)
  untuk \(n \geq 1\).
  \item \(6 \times 2^n + n^3 = \Omega(2^n)\) karena \(6 \times 2^n+n^3
      \geq 2^n\) untuk \(n \geq 1\). Perhatikan bahwa \[6 \times
      2^n+n^3 = \Omega(1)\] akan tetapi batas bawah itu kurang ketat.
      Karenanya kita \textbf{tidak akan} mengatakan \(6 \times 2^n +
          n^3 = \Omega(1)\).
  \item \(150=\Omega(1)\).
\end{enumerate}

Untuk menyatakan batas atas dan batas bawah sekaligus, kita gunakan
notasi Theta-Besar: \(\Theta\).

Definisi:

\(T(n) = \Theta (h(n))\) jika dan hanya jika ada konstanta positif
\(c_1\), \(c_2\), dan \(n_0\) sedemikian sehingga \[c_1 h(n) \leq T(n)
  \leq c_2 h(n)\] apabila \(n \geq n_0\).

%% Ilustrasi yang menggambarkan \Theta(n).

Contoh:
\(3n+2 = \Theta(n)\) karena \[3n+2 \geq 3n\] untuk semua \(n \geq 2\)
  dan \[3n+2 \leq 4n\] untuk semua \(n \geq 2\) dengan \(c_1=3\),
  \(c_2=4\), dan \(n_0=2\).

Notasi Theta-Besar lebih presisi dibandingkan dengan notasi O dan
\(\Omega\), karena sekaligus menyangkut batas atas dan batas bawah.


